HDU2019多校第四场


AND Minimum Spanning Tree

题目链接:HDU6614
题意: $n$ 个点的完全图,两点边权 $ w(u,v)=u \; and \; v $ ,求其最小生成树,并输出每个节点的父亲( $1$ 为根,字典序最小)。
数据范围: $2 \le n \le 200000$
时限: $1s$
题解:
  考虑 $1,2,4,…,2^{k},$这些数,对于 $2^{k}$ 当且仅当第 $k$ 位才为 $1$ ,所以只要是第 $k$ 位为 $0$ 的数去与它相连,边权就为 $0$ 。因为要求字典序最小,从最低位开始枚举即可,若找不到这样的数与其相连,就直接连向 $1$ ,保证边权最小。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include<bits/stdc++.h>
using namespace std;
inline int read(){
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
const int maxn=2e5+5;
int prt[maxn];
int main(){
int T=read();
while(T--){
int n=read(),ans=0;
for(int i=2;i<=n;i++){
bool ok=false;
for(int k=0;k<18;k++){
if((i>>k)&1)continue;
int f=(1<<k);
if(f>n)break;
ok=true;
prt[i]=f;
break;
}
if(!ok){
ans+=(i&1);
prt[i]=1;
}
}
cout<<ans<<"\n";
for(int i=2;i<=n-1;i++)cout<<prt[i]<<" ";
cout<<prt[n]<<"\n";
}
return 0;
}


Colored Tree

题目链接:HDU6615
题意: $n$ 个点的树,每个节点都有一个颜色 $c$ , $q$ 次操作,修改一个点的颜色或询问有多少棵子树里恰好有 $k$ 种颜色。
数据范围: 多组数据 $1 \le T \le 5$ , $1 \le n,q,c \le 100000$
时限: $7s$
题解:
  考虑DFS序,预处理出每个子树中有多少种颜色,对DFS序分块,记 $sum_{i,j}$ 为第 $i$ 块恰好有 $j$ 种颜色的子树个数。对于修改点 $u$ ,在DFS序上找到其同种颜色的前驱和后继,能影响到的点只能到两 $LCA$ 深度较深的一个,采用树剖修改,对块打标记即可。
ps.HDU上这道题的数据应该有误。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
#include<bits/stdc++.h>
using namespace std;
inline int read(){
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
const int maxs=600;
const int maxn=1e5+5;
struct edge{
int to,next;
}e[maxn*2];
int n,q;
int h[maxn],cnt;
inline void addedge(int u,int v){
e[++cnt]=(edge){v,h[u]}; h[u]=cnt;
}
int prt[maxn],siz[maxn],dep[maxn],son[maxn];
int top[maxn];
void Dfs1(int x){
siz[x]=1;
for(int i=h[x];i;i=e[i].next){
int y=e[i].to;
if(y==prt[x])continue;
prt[y]=x; dep[y]=dep[x]+1;
Dfs1(y);
siz[x]+=siz[y];
if(siz[y]>siz[son[x]])son[x]=y;
}
}
int dfn[maxn],mp[maxn],st[maxn],ed[maxn],sign;
void Dfs2(int x,int tp){
top[x]=tp;
dfn[x]=st[x]=++sign;
mp[sign]=x;
if(son[x])Dfs2(son[x],tp);
for(int i=h[x];i;i=e[i].next){
int y=e[i].to;
if(y==prt[x]||y==son[x])continue;
Dfs2(y,y);
}
ed[x]=sign;
}
struct BIT{
int c[maxn];
int lowbit(int x){return x&(-x);}
void add(int x,int d){
for(int i=x;i<=n;i+=lowbit(i))c[i]+=d;
}
int get(int x){
int res=0;
for(int i=x;i;i-=lowbit(i))res+=c[i];
return res;
}
void clear(){
for(int i=0;i<=n;i++)c[i]=0;
}
}bit;
int temp[maxn],col[maxn],lst[maxn];
vector<int>sub[maxn];
set<int>S[maxn];
int num[maxn];
int block,mx,bel[maxn],sum[maxn/maxs+5][maxn];
inline void pre(){
for(int i=1;i<=n;i++)sub[ed[i]].push_back(st[i]);
for(int i=1;i<=n;i++){
bit.add(i,1);
if(lst[col[i]])bit.add(lst[col[i]],-1);
lst[col[i]]=i;
for(int j=0;j<(int)sub[i].size();j++){
int x=sub[i][j];
num[x]=bit.get(i)-bit.get(x-1);
}
}
block=maxs;
for(int i=1;i<=n;i++){
bel[i]=(i-1)/block+1;
mx=max(mx,bel[i]);
sum[bel[i]][num[i]]++;
}
for(int i=1;i<=n;i++)S[col[i]].insert(i);
}
inline int lca(int u,int v){
while(top[u]!=top[v]){
if(dep[top[u]]<dep[top[v]])swap(u,v);
u=prt[top[u]];
}
if(dep[u]>dep[v])swap(u,v);
return u;
}
int dlt[maxn/maxs+5];
inline void update(int u,int v,int f){
for(int i=bel[u]+1;i<=bel[v]-1;i++)dlt[i]+=f;
if(bel[u]==bel[v]){
for(int i=u;i<=v;i++){
sum[bel[u]][num[i]]--;
num[i]+=f;
sum[bel[u]][num[i]]++;
}
}else{
for(int i=u;i<=block*bel[u];i++){
sum[bel[u]][num[i]]--;
num[i]+=f;
sum[bel[u]][num[i]]++;
}
for(int i=block*(bel[v]-1)+1;i<=v;i++){
sum[bel[v]][num[i]]--;
num[i]+=f;
sum[bel[v]][num[i]]++;
}
}
}
inline void addtag(int u,int v,int f){
while(top[u]!=top[v]){
update(dfn[top[u]],dfn[u],f);
u=prt[top[u]];
}
if(u==v)return;
update(dfn[v]+1,dfn[u],f);
}
inline void solve(){
while(q--){
int type=read();
if(type==1){
int u=read(),v=0,t=0,k=read();
int c=col[dfn[u]];
if(c==k)continue;
set<int>::iterator me,it;
me=it=S[c].lower_bound(dfn[u]);
it++;
if(it!=S[c].end())t=lca(u,mp[*it]);
if(me!=S[c].begin()){
me--;
v=lca(u,mp[*me]);
if(dep[v]>dep[t])t=v;
}
addtag(u,t,-1);
t=0;
it=S[k].upper_bound(dfn[u]);
if(it!=S[k].end())t=lca(u,mp[*it]);
if(it!=S[k].begin()){
it--;
v=lca(u,mp[*it]);
if(dep[v]>dep[t])t=v;
}
addtag(u,t,1);
S[c].erase(dfn[u]);
S[k].insert(dfn[u]);
col[dfn[u]]=k;
}
if(type==2){
int k=read(),ans=0;
for(int i=1;i<=mx;i++)ans+=sum[i][k-dlt[i]];
cout<<ans<<"\n";
}
}
}
inline void Clear(){
cnt=sign=0;
for(int i=0;i<=n;i++){
h[i]=0;
prt[i]=bel[i]=son[i]=dep[i]=0;
top[i]=st[i]=ed[i]=dfn[i]=mp[i]=0;
lst[i]=num[i]=col[i]=temp[i]=0;
S[i].clear(); sub[i].clear();
}
for(int i=0;i<=mx;i++){
dlt[i]=0;
for(int j=0;j<=n;j++)sum[i][j]=0;
}
mx=0;
bit.clear();
}
int main(){
int T=read();
while(T--){
n=read(); q=read();
for(int i=1;i<n;i++){
int u=read(),v=read();
addedge(u,v);
addedge(v,u);
}
for(int i=1;i<=n;i++)temp[i]=read();
dep[1]=1;
Dfs1(1);
Dfs2(1,1);
for(int i=1;i<=n;i++)col[dfn[i]]=temp[i];
pre();
solve();
Clear();
}
return 0;
}


Divide the Stones

题目链接:HDU6616
题意: $n$ 堆石头,第 $i$ 堆重量为 $i$ ,要求恰好分为 $k$ 堆,使每堆重量相同,保证 $k$ 为 $n$ 的约数。
数据范围: 多组数据 $1 \le T \le 100$ , $1 \le n \le 100000$ ,$\sum_{n} \le 500000$
时限: $3s$
题解:
  若 $k$ 无法整除 $\frac{n(n+1)}{2}$ 或 $n=k$ 时显然无解。
  现在只用考虑 $n=2k$ 和 $n=3k$ 的情况,因为对于 $n=ak$ 的情况可以将 $[(a-1)k-k+1,ak]$ 通过两两匹配变为 $n=(a-2)k$ 的情况。
   $n=2k$ ,收尾相加即可。
   $n=3k$ ,观察 $n=9,15$ 的结果不难发现,就是将最后一层奇偶分开即可。如图
hdu6616

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include<bits/stdc++.h>
using namespace std;
inline int read(){
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
typedef long long ll;
const int maxn=1e5+5;
int k;
vector<int>ans[maxn];
inline bool check(ll n){
ll sum=n*(n+1)/2;
if(sum%k)return true;
if(k==n)return true;
return false;
}
bool ok;
void solve(int n){
if(n==2*k){
for(int i=1;i<=k;i++){
ans[i].push_back(i);
ans[i].push_back(n-i+1);
}
return;
}
if(n==3*k){
if(k%2==0){ok=true;return;}
int y=2; ll sum=(ll)n*(n+1)/(2*k);
for(int i=1;i<=k;i++){
int x=n-i+1;
ans[i].push_back(x);
ans[i].push_back(y);
ans[i].push_back(sum-x-y);
y+=2; if(y>k)y=1;
}
return;
}
int A=n/k;
for(int i=1;i<=k;i++){
ans[i].push_back(A*k-i+1);
ans[i].push_back((A-1)*k-(k-i));
}
solve((A-2)*k);
}
inline void putans(int n){
if(ok){puts("no");return;}
for(int i=1;i<=k;i++){
for(int j=0;j<ans[i].size();j++)cout<<ans[i][j]<<" ";
cout<<"\n";
}
}
int main(){
int T=read();
while(T--){
int n=read();k=read();
if(k==1){
puts("yes");
for(int i=1;i<=n;i++)cout<<i<<" ";cout<<"\n";
continue;
}
if(check(n)){puts("no");continue;}
puts("yes");
ok=false;
solve(n); putans(n);
for(int i=1;i<=k;i++)ans[i].clear();
}
return 0;
}


Just an Old Puzzle

题目链接:HDU6620
题意: 给出一个 $16$ 数码拼图游戏,询问 $120$ 步内能否还原。
数据范围: 多组数据 $1 \le T \le 100000$
时限: $2s$
题解:
给出结论:
  1.将各个格子(包括空白格子,其数字为 $16$ )中的数字从左至右从上至下排成一个数列,然后计算该数列的逆序对数。
  2.计算空白格子的位置到右下角的距离,如果右下角的坐标为 $(n,n)$ ,空白格子所在位置坐标为 $(x,y)$ ,则距离 $d=(n-x)+(n-y)$ 。
  3.如果上述逆序对数与距离同为奇数或同为偶数,则排列有解,如果一奇一偶,则排列无解。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include<bits/stdc++.h>
using namespace std;
inline int read(){
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
int A[20];
int main(){
int T=read();
while(T--){
int cnt1=0,cnt2=0;
for(int i=1;i<=4;i++)
for(int j=1;j<=4;j++){
int x=(i-1)*4+j;
A[x]=read();
if(!A[x])cnt2=(4-i)+(4-j),A[x]=16;
}
for(int i=1;i<=16;i++)
for(int j=i+1;j<=16;j++)if(A[i]>A[j])cnt1++;
if(cnt1%2==cnt2%2)puts("Yes");
else puts("No");
}
return 0;
}


K-th Closest Distance

题目链接:HDU6621
题意: 长度为 $n$ 的数列, $m$ 次询问,每次询问 $i \in [L,R]$ , $\mid p-a_{i} \mid$ 中的第 $k$ 小值,强制在线。
数据范围: 多组数据 $1 \le T \le 3$ , $1 \le n,m \le 100000$ ,$a_{i} \le 1000000$
时限: $15s$
题解:
  二分出 $mid$ ,用主席树询问 $[p-mid,p+mid]$ 中元素个数是否大于等于 $k$ 即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include<bits/stdc++.h>
using namespace std;
inline int read(){
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
const int inf=1e6;
const int maxn=2e5+5;
int n,m,w[maxn];
int cnt,rt[maxn],sum[maxn*30],ls[maxn*30],rs[maxn*30];
int Insert(int L,int R,int u,int val){
int v=++cnt;
sum[v]=sum[u]+1;
if(L==R)return v;
ls[v]=ls[u]; rs[v]=rs[u];
int mid=(L+R)>>1;
if(val<=mid)ls[v]=Insert(L,mid,ls[u],val);
else rs[v]=Insert(mid+1,R,rs[u],val);
return v;
}
int tot;
void query(int L,int R,int l,int r,int u,int v,int lim){
if(tot>=lim)return;
if(L>r||R<l)return;
if(l<=L&&r>=R){
tot+=sum[v]-sum[u];
return;
}
int mid=(L+R)>>1;
query(L,mid,l,r,ls[u],ls[v],lim);
query(mid+1,R,l,r,rs[u],rs[v],lim);
}
inline void Clear(){
for(int i=1;i<=n;i++)rt[i]=0;
for(int i=1;i<=cnt;i++)sum[i]=ls[i]=rs[i]=0;
cnt=0;
}
int main(){
int T=read();
while(T--){
n=read();m=read();
for(int i=1;i<=n;i++){
w[i]=read();
rt[i]=Insert(0,inf,rt[i-1],w[i]);
}
int ans=0;
for(int i=1;i<=m;i++){
int L=read()^ans,R=read()^ans,p=read()^ans,k=read()^ans;
int l=0,r=inf;
while(l<=r){
int mid=(l+r)>>1;
tot=0;
query(0,inf,p-mid,p+mid,rt[L-1],rt[R],k);
if(tot>=k){ans=mid;r=mid-1;}
else l=mid+1;
}
cout<<ans<<"\n";
}
Clear();
}
return 0;
}


Minimal Power of Prime

题目链接:HDU6623
题意: 求出 $n(n>1)$,所有质因子幂中的最小值。
数据范围: 多组数据 $1 \le T \le 50000$ , $1 \le n \le 10^{18}$
时限: $1s$
题解:
  从数据大小上分析,我们需要一个复杂度为 $O(n^{\frac{1}{5}})$ 的算法。不妨通过打表,先分解 $n^{\frac{1}{5}}$ 范围内的素数,如果分解后为 $1$ ,则答案为分解时的最小值,否则只剩下 $p^{4},p^{3},p^{2},p^{2}q^{2}$ 和答案为 $1$ 的情况。因为开三次方会有精度问题,可以通过二分来判断。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include<bits/stdc++.h>
using namespace std;
inline int read(){
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
typedef long long ll;
const int inf=1e9;
const int maxn=4000;
int p[maxn],vis[maxn],cnt;
inline void pre(){
for(int i=2;i<maxn;i++){
if(!vis[i])p[++cnt]=i;
for(int j=1;j<=cnt;j++){
if(i*p[j]>=maxn)break;
vis[i*p[j]]=1;
if(i%p[j]==0)break;
}
}
}
inline bool check(ll n){
ll L=1,R=1e6;
while(L<=R){
ll mid=(L+R)>>1;
ll m=mid*mid*mid;
if(m==n)return true;
if(n>m)L=mid+1;
else R=mid-1;
}
return false;
}
int main(){
pre();
int T=read();
while(T--){
int ans=inf;
ll n;scanf("%lld",&n);
for(int i=1;i<=cnt;i++){
int sum=0;
while(n%p[i]==0){
n/=p[i];
sum++;
}
if(sum)ans=min(ans,sum);
}
if(n==1)cout<<ans<<"\n";
else{
ll p2=sqrt(n),p4=sqrt(p2);
if(p4*p4*p4*p4==n)ans=min(ans,4);
else if(p2*p2==n)ans=min(ans,2);
else if(check(n))ans=min(ans,3);
else ans=1;
cout<<ans<<"\n";
}
}
return 0;
}

0%